import java.util.LinkedList;
import java.util.Queue;

public class Solution3 {
    public boolean[][] fg;
    public int numIslands(int[][] grid) {
        int ans=0;
        fg=new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1){
                    ans++;
                    fg[i][j]=true;
                    grid[i][j]=0;
                    dfs(grid,i,j);
                }
            }
        }

        return ans;
    }

    private void dfs(int[][] grid, int a, int b) {
        int[] dx={1,0,-1,0};
        int[] dy={0,1,0,-1};
        Queue<Integer> q=new LinkedList<>();
        q.offer(a);
        q.offer(b);

        while (!q.isEmpty()){
            int qx=q.poll();
            int qy=q.poll();
            for (int i = 0; i < 4; i++) {
                int x=qx+dx[i];
                int y=qy+dy[i];
                if(x>=0 && x< grid.length && y>=0 && y<grid[0].length && grid[x][y]==1 && !fg[x][y]){
                    q.offer(x);
                    q.offer(y);
                    grid[x][y]=0;
                    fg[x][y]=true;
                }
            }
        }
    }
}

